package com.example.Arithmetic.Lettcode;

import com.example.Arithmetic.Arithmetic.TreeNode;

import java.util.LinkedList;

/**
 * 日期：2023/10/18
 * 时间：8:42
 * 描述：二叉树范围之和
 */
public class E04Lettcode938 {
    //    中序迭代
    public int rangeSumBST(TreeNode root, int low, int high) {
        TreeNode node = root;
        LinkedList<TreeNode> list = new LinkedList<>();
        int sum = 0;
        while (node != null || !list.isEmpty()) {
            if (node != null) {
                list.push(node);
                node = node.left;
            } else {
                TreeNode<Integer> pop = list.pop();
                if (pop.val > high) {
                    break;
                }
                if (pop.val >= low) {
                    sum += pop.val;
                }
                node = pop.right;
            }
        }
        return sum;
    }

    //    递归
    public int rangeSumBST1(TreeNode<Integer> root, int low, int high) {
        if (root == null) {
            return 0;
        }
        int a = rangeSumBST1(root.left, low, high);
        int b = 0;
        if (root.val >= low && root.val <= high) {
            b = root.val;
        }
        return a + b + rangeSumBST1(root.right, low, high);
    }

    //    上下限递归
    public int rangeSumBST2(TreeNode<Integer> root, int low, int high) {
        if (root == null) {
            return 0;
        }
//        不符合范围
        if (root.val < low) {
            return rangeSumBST2(root.right, low, high);
        }
        if (root.val > high) {
            return rangeSumBST2(root.left, low, high);
        }
//        符合范围
        return root.val + rangeSumBST2(root.left, low, high) + rangeSumBST2(root.right, low, high);
    }
}

